// levenshtein.cpp
// Implementation of the Levenshtein Edit Distance algorithm.
//
// This source is based on the algorithm and source code presented by
// Michael Gilleland at Merriam Park Software, http://www.merriampark.com/ld.htm
//
// Converted to SQL Server 2000 Extended Stored Procedure by
// Michael Coles, MCDBA
//
#include <string.h>
#include <malloc.h>
#include <lev.h>

// Minimum3
// Returns the minimum of three numbers
//
// Parameters:
//		int a			an int number
//		int b			an int number
//		int c			an int number
//
// Returns:
//		int				The minimum of a, b or c.
//
int Levenshtein::Minimum3 (int a, int b, int c)
{
	if (b < a)
		a = b;
	if (c < a)
		a = c;
	return a;
}

// GetCellPointer
// Returns a cell pointer to the specified col and row in the array
//
// Parameters:
//		int *base		The pointer to the base of the array
//		int column		The specified column
//		int row			The specified row
//		int numcolumns	The number of columns in the array
//
// Returns:
//		int *			The pointer to the specified col and row in the array
int *Levenshtein::GetCellPointer (int *base, int column, int row, int numcolumns)
{
	return base + column + (row * (numcolumns + 1));
}
// GetCell
// Returns the contents of the cell at the specified column and row
//
// Parameters:
//		int *base		Pointer to the base of the array
//		int column		The specified column
//		int row			The specified row
//		int numcolumns	The number of columns in the array
//
// Returns:
//		int				Value at the specified column and row of the array
//
int Levenshtein::GetCell (int *base, int column, int row, int numcolumns)
{
	int *cell;
	cell = GetCellPointer(base, column, row, numcolumns);
	return *cell;
}

// PutCell
// Puts the value passed into the specified cell of the array
//
// Parameters:
//		int *base		Pointer to the base of the array
//		int column		The specified column
//		int row			The specified row
//		int numcolumns	The number of columns in the array
//		int value		The value to place into the array
//
void Levenshtein::PutCell(int *base, int column, int row, int numcolumns, int value)
{
	int *cell;

	cell = GetCellPointer(base, column, row, numcolumns);
	*cell = value;
}
// UCase
// Converts a byte from lowercase to uppercase
//
// Parameters:
//		BYTE c			The character to convert
//
// Returns:
//		BYTE			The uppercase character
//
BYTE Levenshtein::UCase(BYTE c) {
	if (c >= 'a' && c <= 'z')
		c = c - 'a' + 'A';
	return (c);
}

// GetDistance
// Calculates the Levenshtein distance between two strings

int Levenshtein::GetDistance (BYTE *string1, ULONG length1, BYTE *string2, ULONG length2)
{
	int *base = NULL;		// pointer to matrix
	ULONG i;		// iterates through string1
	ULONG j;		// iterates through string2
	BYTE string1_c;	// ith character of string1
	BYTE string2_c;	// jth character of string2
	int cost; // cost
	int result; // result
	int cell; // contents of target cell
	int above; // contents of cell immediately above
	int left; // contents of cell immediately to left
	int diag; // contents of cell immediately above and to left
	int arraysize;	// number of cells in matrix

	// If either string is length 0, the result is the length of the
	// other string
	if (length1 == 0)
		return length2;
	if (length2 == 0) 
		return length1;

	// Create our array
	arraysize = (length1 + 1) * (length2 + 1) * sizeof(int);
	base = (int *)malloc(arraysize);

	// Populate the top row with increasing numbers
	for (i = 0; i <= length1; i++)
		PutCell (base, i, 0, length1, i);
	for (j = 0; j <= length2; j++)
		PutCell (base, 0, j, length1, j);
	// Now we iterate the two strings, comparing them and calculating
	// the edit distance between them
	for (i = 1; i <= length1; i++) {
		string1_c = UCase(*(string1 + i - 1));
		for (j = 1; j <= length2; j++) {
			string2_c = UCase(*(string2 + j - 1));
			// If the two characters are the same, the cost is 0
			// otherwise it's 1
			if (string1_c == string2_c) {
				cost = 0;
			} else {
				cost = 1;
			}
			// Get the values for the above, left and diagonal edit distances
			above = GetCell(base, i-1, j, length1);
			left = GetCell(base, i, j-1, length1);
			diag = GetCell(base, i-1, j-1, length1);
			// Calculate the minimum of the cell above, to the left and 
			// diagonal + cost
			cell = Minimum3 (above + 1, left + 1, diag + cost);
			// Update the array
			PutCell (base, i, j, length1, cell);
		}
	}
	// Calculate our final result
	result = GetCell (base, length1, length2, length1);
	if (base != NULL)
		free (base);
	base = NULL;
	return result;
}
